package Dynamic;

import java.util.Arrays;

/**
 * 利用动态规划算法，解决01背包问题。
 */
public class DynamicKnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1,4,3}; // 每个物品的重量
        int[] val = {1500, 3000, 2000}; // 物品的价值  val[i]
        int m = 4; // 背包的容量
        int n = w.length; // 物品的个数
        // 创建二维数组
        // v[i][j]  表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];

        // 根据前面的公式来动态规划处理
        //将商品，依次递增，i：表示某个商品
        for (int i = 1; i < v.length; i++) {//从1开始，因为这是数组下标
            //将背包重量的容量依次递增，计算每一次容量可以放置的最大价值
            for (int j = 1; j < v[0].length; j++) {
                if (w[i-1] > j) {//若当前添加商品的重量，大于背包的容量
                    //直接将上一个的单元格价值装入进去
                    v[i][j] = v[i - 1][j];
                }else {
                    //若当前添加商品的重量，小于等于背包的容量
                    //则先将当前商品添加进去，再去将之前的结果里面，找与多余空间一样大的添加结果，两者相加就是当前应该添加的结果
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }

        }

        //打印这个数组
        for (int[] ints : v) {
            System.out.println(Arrays.toString(ints));
        }

    }

}
